// =====================================================================================
//
//       Filename:  geometrie.h
//
//    Description:  Description de structures géométriques utilisées pour la
//					géolocalisation des objets de la carte
//
//        Version:  1.0
//        Created:  11/08/2009 18:00:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#ifndef GEOMETRIE_H_INC
#define GEOMETRIE_H_INC

#include	<iostream>
#include	<deque>
#include	<cmath>
#include	<string>
#include	<exception>

using namespace std;

/**
 * \class GeometryException
 * \brief Exception soulevée lors d'une erreur sur des opérations géométriques
 *
 * La classe permet de gérer les erreurs d'utilisation des opérations sur les structures géométriques.
 */
class GeometryException:public exception {
	public:
		/**
		 * \brief Ensemble des codes d'erreur possibles
		 *
		 * L'énumération rassemble les codes d'erreur qui peuvent être retournés lorsqu'une opération sur des objets géométriques a généré une erreur.
		 */
		enum Code {
			BAD_OPERATION	//!< Opération incorrecte
			} code;	//!< Code de l'erreur
		string message;	//!< Message à retourner à l'utilisateur
		GeometryException(Code pcode,string pmessage=""):code(pcode),message(pmessage) {}	//!< Constructeur standard avec message d'erreur
		~GeometryException() throw() {}	//!< Destructeur standard
		const char* what() const throw();	//!< Retourne la nature de l'erreur
};

/**
 * \class Point
 * \brief Définition d'un point
 *
 * La structure est une représentation générique des coordonnées d'un point dans un espace à k dimensions.
 */
class Point {
	public:
		double x;	//!< Abscisse du point
		double y;	//!< Ordonnée du point

		/**
		 * \brief Constructeur standard
		 *
		 * Le constructeur initialise la structure et définit ses coordonnées.
		 * \param xx Abscisse du point
		 * \param yy Ordonnée du point
		 */
		Point(double xx,double yy):x(xx),y(yy) {}

		void affiche(ostream& out) const;	//!< Affichage sur le flux de sortie out

		/**
		 * \brief Retourne un tableau contenant les coordonnées géométriques de l'intersection
		 *
		 * La fonction retourne dans son paramètre un tableau de taille 2 contenant les coordonnées de l'intersection représentée par la structure. Elle est notamment utilisée par l'algorithme de recherche du plus proche voisin, qui ordonne ces tableaux de coordonnées dans un arbre Kd_tree.
		 * Le tableau spécifié en argument doit au préalable être alloué en mémoire.
		 * \param res Tableau des coordonnées de l'intersection
		 */
		void coordonnees(double res[]) const;

		/**
		 * \brief Retourne le carré de la distance du point au second point donné en argument
		 *
		 * La fonction calcule le carré de la distance euclidienne de l'instance au point donné en argument.
		 * \param p Second point
		 * \return Carré de la distance au point p
		 */
		double carre_distance(const Point &p) const;

		/**
		 * \brief Retourne le carré de la distance du point au second point dont les coordonnées sont mentionnées en argument
		 *
		 * La fonction calcule le carré de la distance euclidienne de l'instance de la classe au point dont les coordonnées sont données en argument. Elle est plus rapide que la fonction précédente si la structure Point n'est pas disponible.
		 * \param px Abscisse du second point
		 * \param py Ordonnée du second point
		 * \return Carré de la distance au second point
		 */
		double carre_distance(const double &px,const double &py) const {
			double dx=px-x;
			double dy=py-y;
			return dx*dx+dy*dy;
		}

		/**
		 * \brief Retourne le carré de la distance du point à la droite passant par les deux points spécifiés en argument
		 *
		 * La fonction calcule le carré de la distance euclidienne de l'instance à la droite passant par les deux points donnés en argument.
		 * \param a Premier point définissant la droite
		 * \param b Second point définissant la droite
		 * \return Carré de la distance à la droite (ab)
		 */
		double carre_distance(const Point &a,const Point &b) const;

		/**
		 * \brief Retourne le carré de la distance du point au segment dont les extrémités sont données
		 *
		 * La fonction calcule le carré de la distance euclidienne de l'instance au segment dont les extrémités sont données en argument.
		 * \param a Première extrémité du segment
		 * \param b Seconde extrémité du segment
		 * \return Carré de la distance au segment [ab]
		 */
		double carre_distance_segment(const Point &a,const Point &b) const;

		/**
		 * \brief Retourne la distance du point au second point donné en argument
		 *
		 * La fonction calcule la distance euclidienne de l'instance au point donné en argument.
		 * \param p Second point
		 * \return Distance au point p
		 */
		double distance(const Point &p) const {return sqrt(carre_distance(p));}

		/**
		 * \brief Retourne la distance du point à la droite passant par les deux points donnés en paramètres
		 *
		 * La fonction calcule la distance euclidienne de l'instance à la droite passant par les deux points spécifiés en arguments.
		 * \param a Premier point définissant la droite
		 * \param b Second point définissant la droite
		 * \return Distance à la droite (ab)
		 */
		double distance(const Point &a,const Point &b) const {return sqrt(carre_distance(a,b));}

		/**
		 * \brief Retourne la distance du point au segment dont les extrémités sont données
		 *
		 * La fonction calcule la distance euclidienne de l'instance au segment dont les extrémités sont données en argument.
		 * \param a Première extrémité du segment
		 * \param b Seconde extrémité du segment
		 * \return Distance au segment [ab]
		 */
		double distance_segment(const Point &a,const Point &b) const {return sqrt(carre_distance_segment(a,b));}
};

/**
 * \fn ostream& operator<< (ostream& out,const Point &p);
 * \brief Affiche le point sur un flux de sortie
 *
 * La fonction affiche les coordonnées du point p sur le flux de sortie out, puis retourne ce même flux de sortie.
 * \param out Flux de sortie sur lequel afficher le point
 * \param p Point à afficher
 * \return Flux de sortie non modifié
 */
ostream& operator<< (ostream& out,const Point &p);

/**
 * \fn bool operator< (const Point &p1,const Point &p2)
 * \brief Opérateur de comparaison entre deux points, introduisant une relation d'ordre totale dans l'espace des points
 *
 * La fonction compare les deux points p1 et p2, selon la relation d'ordre décrite dans Reseau::cherche.
 * \param p1 Premier point à comparer
 * \param p2 Second point à comparer
 * \return true si p1<p2, false sinon
 */
bool operator< (const Point &p1,const Point &p2);

/**
 * \fn bool operator== (const Point &p1,const Point &p2)
 * \brief Opérateur de comparaison entre deux points, introduisant une relation d'équivalence dans l'espace des points
 *
 * La fonction compare les deux points p1 et p2
 * \param p1 Premier point à comparer
 * \param p2 Second point à comparer
 * \return true si p1=p2, false sinon
 */
bool operator== (const Point &p1,const Point &p2);

/**
 * \class Polyligne
 * \brief Suite de segments de droites
 *
 * La classe contient une polyligne destinée à représenter un tronçon de route. Il s'agit d'un ensemble de lignes simples dont les extrémités sont liées.
 */
class Polyligne {
	/**
	 * \fn friend ostream& operator<< (ostream& out,const Polyligne &pl);
	 * \brief Affiche la polyligne sur un flux de sortie
	 *
	 * La fonction affiche les coordonnées de la polyligne pl sur le flux de sortie out, puis retourne ce même flux de sortie.
	 * \param out Flux de sortie sur lequel afficher la polyligne
	 * \param pl Polyligne à afficher
	 * \return Flux de sortie non modifié
	 */
	friend ostream& operator<< (ostream& out, const Polyligne &pl);
	public:
		int attributs[3];	//!< Attributs de la polyligne

		/**
		 * \brief Constructeur standard
		 *
		 * Le constructeur crée une polyligne sans initialiser ses attributs.
		 */
		Polyligne():_longueur(0.0) {}

		/**
		 * \brief Constructeur de copie
		 *
		 * Le constructeur crée une nouvelle polyligne en recopiant tous les points et les attributs de la polyligne initiale.
		 * Note : de nouveaux points sont créés pendant le processus. Cela est nécessaire pour éviter d'avoir plusieurs pointeurs sur une même instance d'un point, source de difficultés lors de la libération des ressources.
		 * \param p Polyligne à copier
		 */
		Polyligne(const Polyligne &p);
		~Polyligne();	//!< Destructeur par défaut, libère tous les points contenus
		void affiche(ostream& out) const;	//!< Affichage sur le flux de sortie out

		/**
		 * \brief Retourne la longueur de la polyligne
		 *
		 * La fonction retourne la longueur de la polyligne, qui correspond à la somme des longueurs des segments élémentaires qui la composent.
		 * \return Longueur de la polyligne
		 */
		double longueur() const {return _longueur;}

		/**
		 * \brief Retourne la distance de la polyligne au point passé en argument
		 *
		 * La fonction calcule la distance de la polyligne au point p. Elle s'effectue en un temps proportionnel au nombre de sommets qui composent la polyligne.
		 * \param p Point dont la distance à la polyligne sera calculée
		 * \return Distance du point p à la polyligne courante
		 */
		double distance(const Point &p) const;

		/**
		 * \brief Vide la polyligne et détruit tout son contenu
		 *
		 * La fonction détruit le contenu de la polyligne et libère les ressources associées. Elle est appelée par le destructeur standard.
		 */
		void vide();

		/**
		 * \brief Ajoute un point à la polyligne
		 *
		 * La fonction ajoute un point à la fin de la polyligne, et met à jour sa longueur
		 * \param p Nouveau point à ajouter à la polyligne
		 */
		void ajoute_point(Point *p);

		/**
		 * \brief Retourne l'extrémité initiale de la polyligne
		 *
		 * La fonction retourne un pointeur vers le point qui constitue l'extrémité initiale de la polyligne.
		 * \return Pointeur vers l'extrémité initiale de la polyligne
		 */
		Point* front() const {return _points.front();}

		/**
		 * \brief Retourne l'extrémité finale de la polyligne
		 *
		 * La fonction retourne un pointeur vers le point qui constitue l'extrémité finale de la polyligne.
		 * \return Pointeur vers l'extrémité finale de la polyligne
		 */
		Point* back() const {return _points.back();}

		/**
		 * \brief Retourne un itérateur vers le début de la liste des points
		 *
		 * L'accesseur retourne un itérateur vers le début de la liste des points. La fonction ne sert qu'à cacher l'implémentation de la liste des points.
		 * \return Itérateur au début de la liste des points
		 */
		deque<Point*>::iterator begin() {return _points.begin();}

		/**
		 * \brief Retourne un itérateur vers la fin de la liste des points
		 *
		 * L'accesseur retourne un itérateur vers la fin de la liste des points. La fonction ne sert qu'à cacher l'implémentation de la liste des points.
		 * \return Itérateur à la fin de la liste des points
		 */
		deque<Point*>::iterator end() {return _points.end();}

		/**
		 * \brief Retourne le nombre de points de la polyligne
		 *
		 * L'accesseur retourne le nombre de points de la polyligne. Il ne sert qu'à cacher l'implémentation de la liste des points.
		 * \return Nombre de points de la polyligne
		 */
		size_t num_points() const {return _points.size();}
	private:
		deque<Point*> _points;	//!< Liste des points constitutifs de la polyligne
		double _longueur;	//!< Longueur de la polyligne, mémorisée pour éviter des calculs superflus
};

/**
 * \fn ostream& operator<< (ostream& out,const Polyligne &pl);
 * \brief Affiche la polyligne sur un flux de sortie
 *
 * La fonction affiche les coordonnées de la polyligne pl sur le flux de sortie out, puis retourne ce même flux de sortie.
 * \param out Flux de sortie sur lequel afficher la polyligne
 * \param pl Polyligne à afficher
 * \return Flux de sortie non modifié
 */
ostream& operator<< (ostream& out,const Polyligne &pl);

#endif /* GEOMETRIE_H_INC */
